# 详解见C
class matrix:

    def __init__(self, a):
        self.a = a

def unit():
    return matrix([[1 if i == j else 0 for j in range(6)] for i in range(6)])

def mul(A, B):
    C = matrix([[0] * 6 for i in range(6)])
    for i in range(6):
        for j in range(6):
            for k in range(6):
                C.a[i][j] += A.a[i][k] * B.a[k][j] % mod
                C.a[i][j] %= mod
    return C

def pow(A, n):
    res, tmp = unit(), A
    while n:
        if n & 1: res = mul(res, tmp)
        tmp = mul(tmp, tmp)
        n >>= 1
    return res

def sum(A):
    ans = 0
    for i in range(6):
        for j in range(6):
            ans += A.a[i][j] % mod
            ans %= mod
    return ans

mod = int(1e9 + 7)
dp = matrix([[4] * 6 for i in range(6)])
n, m = map(int, input().split())
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    dp.a[a][(b + 3) % 6] = 0
    dp.a[b][(a + 3) % 6] = 0
dp = pow(dp, n - 1)
ans = (sum(dp) * 4) % mod
print(ans)
'''
from random import randint as r
from random import shuffle as s

mod = int(1e9 + 7)
nn = [(1, 100), (20000, 60000), (int(8e6), int(1e8)), (int(9e8), int(1e9))]
mm = (6, 20)
for ww in range(len(nn)):
    n = r(*nn[ww])
    m = r(*mm)
    s_i = f"{n} {m}\n"
    print(n, m)
    ab = []
    for wi in range(1, 7):
        for wj in range(1, 7):
            ab.append((wi, wj))
    dp = matrix([[4] * 6 for i in range(6)])
    for wi in range(m):
        s(ab)
        a, b = ab.pop()
        s_i += f"{a} {b}\n"
        print(a, b)
        a, b = a - 1, b - 1
        dp.a[a][(b + 3) % 6] = 0
        dp.a[b][(a + 3) % 6] = 0
    dp = pow(dp, n - 1)
    ans = (sum(dp) * 4) % mod
    s_o = f"{ans}"
    print(ans)
    print()
    with open(f"{ww + 1}.in", 'w') as f:
        f.write(s_i)
    with open(f"{ww + 1}.out", 'w') as f:
        f.write(s_o)
'''
# -------------------------------------------------------------------------------

# 比赛环境为python3.8.6版本自带的IDLE，最好早点熟悉一下。。这个东西的提示时有时无

# 菜单栏最右边的Help的Python Docs 比赛时候也可以看，不过建议还是提前多了解了解，

# 比赛的时候至少知道在文档找什么能用的上。
